#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

bool isCover(unordered_map<char, int>& smap, unordered_map<char, int>& tmap) {
    for (auto it2 = tmap.begin(); it2 != tmap.end(); it2++) {
        auto it1 = smap.find(it2->first);
        if (it1 == smap.end() || it1->second < it2->second) return 0;
    }
    return 1;
}

string minWindow(string S, string T) {
    if (T.length() == 0) return "";
    if (T.length() == 1) return (S.find(T) == string::npos) ? "" : T;

    unordered_map<char, int> smap;
    unordered_map<char, int> tmap;
    for (int i = 0; i < T.length(); i++) tmap[T[i]]++;

    int minlen = 0x3f3f3f3f;
    int minleft = -1;
    int left = 0;
    int right = 0;

    while (left < S.length() && !tmap.count(S[left])) left++;
    if (left == S.length() || left == S.length() - 1) return "";
    right = left + 1;
    smap[S[left]]++;

    while (right < S.length()) {
        if (isCover(smap, tmap)) {
            if (right - left < minlen) {
                minleft = left;
                minlen = min(minlen, right - left);
            }
            smap[S[left]]--;
            left++;
            while (left < right && !tmap.count(S[left])) left++;
        } else {
            while (right < S.length() && !tmap.count(S[right])) right++;
            if (right != S.length()) {
                smap[S[right]]++;
                right++;
            }
        }
    }
    if (isCover(smap, tmap)) {
        if (right - left < minlen) {
            minleft = left;
            minlen = min(minlen, right - left);
        }
    }
    if (minleft == -1) return "";
    return S.substr(minleft, minlen);
}

int main() {
    string S = "aa";
    string T = "aa";
    string ans = minWindow(S, T);
    cout << "ans: " << ans << endl;
    return 0;
}
